1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to communication scheduling, and more particularly, to communication scheduling which efficiently transmits/receives control packets required for communication scheduling among nodes.
2. Description of the Related Art
With technological advancements made in sensors, Micro Electro Mechanical Systems (MEMS), low-power electronics, and low-power radio frequency (RF) design, low-priced and low-power miniature sensor nodes capable of being connected through a wireless network have been developed. The sensor nodes include sensing, data processing, and communication components. A great number of sensor nodes may be densely deployed in very close areas so as to form a wireless sensor network, which can be applied to various fields, including military, home networks, environment monitoring, factory management, disaster monitoring, etc. Since it is not required to predetermine the positions of sensor nodes in the sensor network, the sensor nodes can be deployed according to necessity for applications in an unapproachable area or disaster rescue situation. This is because a sensor network protocol has a self-organizing capability, and sensor nodes cooperate with each other.
In addition, a sensor network includes a sensor field, in which sensor nodes are deployed, and a sink which connects the sensor field to an external network. That is, data collected in the sensor field can be transported through the sink.
FIG. 1 is a conceptual view illustrating an example in which communication times are allocated to each node through cross-layer scheduling in a related art sensor network.
After sensor nodes have been deployed in a sensor field, a sink node, i.e., base station (BS), which finally collects information collected by the sensor nodes, floods interest query packets containing information about data to be collected by the sensor nodes. When the interest query packets have been flooded, a network topology with a tree structure is formed.
That is, when the sink node floods the interest query packets to all the sensor nodes, the sink node becomes a source node, and nodes #3, #6, and #10 become destination nodes. Thereafter, each of nodes #3, #6, and #10 transmits the received interest query packets to its neighboring sensor nodes. In this case, nodes #3, #6, and #10 become source nodes, and nodes #2, #4, #9, #7, and #8 become destination nodes. That is, the destination node of node #3 is node #2, the destination nodes of node #6 are nodes #4 and #9, and the destination nodes of node #10 are nodes #7 and #8. When the interest query packets have been continuously transmitted to an end node in the above manner, the tree structure connected by arrows, as shown in FIG. 1, is created.
Thereafter, nodes #1, #5, #9, #7, and #8, which are child nodes, transmit data collected by the respective child nodes to nodes #2, #4, #6, and #10, which are parent nodes thereof. Then, nodes #2, #4, #6, and #10 transmit data to their parent nodes, i.e., to node #3 and BS, and node #3 transmits data to the BS, so that the BS can collect the data.
Therefore, communication scheduling to the sink node (BS) is completed by successively performing the communication scheduling with respect to corresponding parent nodes from the lowest-stage child nodes in the tree structure, so that data collected by the sensor nodes can be efficiently transmitted to the sink node (BS).
Meanwhile, cross-layer scheduling is constructed with a Request To Send (RTS) packet transmitted from a source node to a destination node, a Clear To Send (CTS) packet used by a destination node in order to notify a source node that the destination node has received an RTS packet, a Route SETUP (RSETUP) packet used by a source node in order to notify a destination node of a communication time period representing how much time the source node will need to transmit actual data packets, and an acknowledgement (ACK) packet used by a destination node in order to notify a source node that communication scheduling has been determined.
The cross-layer scheduling includes determining communication time and transmitting a packet according to the determined communication time. The communication time determination is performed only once after nodes have been deployed in a area. In the communication time determination, the nodes use control packets (i.e., RTS, CTS, RSETUP, and ACK packets) in order to make out communication scheduling for communication time. In the cross-layer scheduling, the communication scheduling starts from the lowest-stage node in the topology, since most of the packets must be transmitted to a sink node in an actual sensor network. A more detailed description of the cross-layer scheduling is disclosed in “Cross-Layer Scheduling for Power Efficiency in Wireless Sensor; M. L. Sichitiu”.
A source node, which wants to establish the communication scheduling, sets a node corresponding to its own next hop as a destination node, and transmits an RTS packet to the destination node. The RTS packet transmitted by the source node includes a time value (i.e., time-stamp value) at which the RTS packet is transmitted. The time-stamp value represents a communication start time for transmission of an actual data packet. When the destination node of the RTS packet has successfully received the RTS packet, the destination node transmits a CTS packet to the source node in response to the reception of the RTS packet. After receiving the CTS packet, the source node transmits an RSETUP packet, which includes communication time information about how much time the source node will need to transmit packets, to the destination node. After successfully receiving the RSETUP packet, the destination node determines the communication scheduling based on a time period recorded in the RSETUP packet and the time at which the RTS packet was transmitted.
Thereafter, the destination node transmits an ACK packet to the source node, thereby notifying the source node that the communication scheduling has been determined based on the time period recorded in the RSETUP packet and the time point at which the RTS packet was transmitted. Through such a procedure, the communication scheduling is determined from the lowest-stage nodes to a sink node. After communication time for all nodes has been determined in the communication time determination, the nodes transmit actual data packets during a determined communication time period. That is, a sensor node sets its own transceiver to receive or transmit so as to perform communication when it is time for the sensor node to communicate, and the sensor node maintains its own transceiver in a sleep state so as to save its power when not communicating.
However, when the RTS packet cannot be normally received by a corresponding destination node because a plurality of sensor nodes try to simultaneously transmit RTS packets within a range in which their communication may interfere with each other, or because a hidden node terminal exists, it is impossible to use the time point of the RTS packet transmission in a section for actual data communication. When the RTS packet has not been transmitted or received normally, the source node re-transmits the RTS packet. Repetition of such re-transmissions, causes the sensor node to consume, power unnecessarily.
Also, when a packet loss occurs during the transmission or reception procedure of the control packets (i.e., RTS, CTS, RSETUP, and ACK packets), the transmission or reception procedure must be performed again from the first step of transmitting the RTS packet, thereby unnecessarily consuming more power.
In addition, in the case in which a sensor node is an intermediate node of a routing path, if an RTS packet was lost during a communication scheduling procedure between the intermediate node and a destination node, the intermediate node must again attempt to establish communication scheduling with the destination node after a period of time elapses, so that a time delay may occur when transmitting an actual data packet.
Therefore, a method which can prevent an unnecessary consumption of power due to re-transmission of a packet and reduce a delay time in packet transmission during the transmission or reception procedure of control packets, which are required for communication scheduling of sensor nodes in a sensor network has been developed.